Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.
Example 1:
Input: nums = [1,2,3] Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Example 2:
Input: nums = [0,1] Output: [[0,1],[1,0]]
Example 3:
Input: nums = [1] Output: [[1]]
Constraints:
1 <= nums.length <= 6-10 <= nums[i] <= 10- All the integers of
numsare unique.
Average Rating: 3.77 (91 votes)
Solution
Approach 1: Backtracking
Backtracking is an algorithm for finding all solutions by exploring all potential candidates. If the solution candidate turns to be not a solution (or at least not the last one), backtracking algorithm discards it by making some changes on the previous step, i.e. backtracks and then try again.
Here is a backtrack function
which takes the index of the first integer to consider
as an argument backtrack(first).
- If the first integer to consider has index
nthat means that the current permutation is done. - Iterate over the integers from index
firstto indexn - 1.- Place
i-th integer first in the permutation, i.e.swap(nums[first], nums[i]). - Proceed to create all permutations which starts from
i-th integer :backtrack(first + 1). - Now backtrack, i.e.
swap(nums[first], nums[i])back.
- Place
Complexity Analysis
- Time complexity : O(∑k=1NP(N,k)) where P(N,k)=(N−k)!N!=N(N−1)...(N−k+1) is so-called k-permutations_of_n, or partial permutation.
Here first+1=k for the expression simplicity. The formula is easy to understand : for each k (each first) one performs N(N−1)...(N−k+1) operations, and k is going through the range of values from 1 to N (and first from 0 to N−1).
Let's do a rough estimation of the result : N!≤∑k=1N(N−k)!N!=∑k=1NP(N,k)≤N×N!, i.e. the algorithm performs better than O(N×N!) and a bit slower than O(N!).
- Space complexity : O(N!) since one has to keep
N!solutions.
August 12, 2020 8:54 PM
Thank you for the animation! Makes everything clear!
May 8, 2019 1:11 AM
For the complexity, I think you can explain in this way: in the first level of the tree, you have N options and for each of the option, you have N-1 option, and for each of these N-1 options, you have another N-2 options, so putting them together you would end up N*(N-1)*(N-2).... = N!
Last Edit: January 28, 2019 4:12 PM
I think the time complexity is O(n x n!) instead of O(n!), since you will have n! permutation. And, for each permutation, you run exact n recursive call to reach it. So it should be n x n! ?
Last Edit: September 21, 2019 11:49 AM
First, I think the time complexity should be N x N!.
Initially we have N choices, and in each choice we have (N - 1) choices, and so on. Notice that at the end when adding the list to the result list, it takes O(N).
Second, the space complexity should also be N x N! since we have N! solutions and each of them requires N space to store elements.
April 11, 2019 4:57 PM
honestly, i dont really know how to analyze the time complexity of this approach. I understand the nPk part, but how can to come up with the summation and how can i present it to the interviewer?
June 10, 2019 9:45 PM
For those interested, this is called Heap's Algorithm.
May 8, 2019 1:59 PM
Anyone can explain why the there should be output.append(nums[:]) but not nums?
February 7, 2019 3:13 AM
why we need the second swap?
March 27, 2019 8:58 PM
Hello,
Can anyone explain why space complexity is O(N!) (factorial here) ? Shouldn't it be O(N) only (the depth of recursive tree) for Java program at least ?
My thinking here: At every index i, we go down the depth level from (i+1) to N and recurse back, pop off stack and go down path (i+2) to N and recurse back and so on.. Based on diagram also, we go at most N levels down and recurse back before going to another path. So I was thinking we will have a balanced tree kind of situation here. Please correct me if I'm wrong.
Secondly, when we reach last level shouldn't we consider time complexity of creating a new ArrayList of N numbers to be added to result ?
February 17, 2020 11:36 AM
For the space complexities, I think you're mixing two different types of space complexities. One is the additional memory it uses to solve a problem. For this question, since the nature of the problem is a DFS, so that space complexity is O(N).
For your analysis of O(N!), it is the actual space complexity for the solution itself....
xxxxxxxxxxclass Solution {public: // Backtracking vector<vector<int>> permute(vector<int>& nums) { vector<vector<int>>res; vector<int>temp; solve(nums, res, temp); return res; } void solve(vector<int>& nums, vector<vector<int>>& res, vector<int>temp) { if(temp.size() == nums.size()) { res.push_back(temp); return; } for(int i=0;i<nums.size();i++) { auto it = find(temp.begin(), temp.end(), nums[i]); if(it != temp.end()) continue; // element already exists so we skip it temp.push_back(nums[i]); solve(nums, res, temp); temp.pop_back(); } }};